package uk.org.landeg.euler.problems.unported;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

import org.apache.commons.lang.StringUtils;

public class Utils {
	static Double goldenRatio = null;
	static Double goldenRatio3 = null;
	public static double getGoldenRatio () {
		if (goldenRatio == null) {
			goldenRatio = 0.5 * (1.0 + Math.sqrt(5.0));
		}
		return goldenRatio;
	}
	
	public static double getGoldenRatio3 () {
		if (goldenRatio3 == null) {
			goldenRatio3 = Math.pow(getGoldenRatio(), 3.0);
		}
		return goldenRatio3;
	}
	
	public static long sumSequence (long start, long end) {
		return (start + end) * (end-start + 1)/ 2;
	}
	
	public static ArrayList<Long> fibonacci (long max) {
		long a,b,tmp;
		ArrayList<Long> ret = new ArrayList<Long>();
		ret.add(1L);
		a = 1; b = 2;
		while (b <= max) {
			ret.add(b);
			tmp = b;
			b = a+b;
			a = tmp;
		}
		return ret;
	}
	
	public static long nextFibonacci (long n) {
		return  (long)((n  * getGoldenRatio()) + 0.5);
	}
	
	public static long sumOfSquares (int n) {
		return n * (2 *n +1) * (n+1) / 6;
	}
	
	public static ArrayList<Long> getPrimes (long max) {
		return getPrimes(0,max,null);
	}
	
	public static ArrayList<Long> getPrimes (long start, long max, ArrayList<Long> primes) {
		if (primes == null) {
			primes = new ArrayList<Long>(); 
		} else {
			start = Collections.max(primes);
		}
		long prime = (start > 2) ? start : 2;
		primes.add(2L);
		boolean isprime;
		long maxTest;
		while (prime <= max) {
			maxTest = (long)(Math.sqrt(prime) +1);
			isprime = true;
			for (long test : primes) {
				if (test > maxTest) {
					break;
				}
				if (prime % test == 0) {
					isprime = false;
					break;
				}
			}
			if (isprime) {
				primes.add(prime);
			}
			prime++;
		}
		return primes;
	}
	
	public static Map<Long, Integer> getPrimeFacors (long n) {
		long prime = -1;
		Map<Long,Integer> ret = new HashMap<Long, Integer>();
		ArrayList<Long> primes = getPrimes(100);
		int primeId = 0;
		
		while (n > 1) {
			if (prime == -1) {
				primeId++;
				if (primeId >= primes.size()) {
					getPrimes(0, Collections.max(primes) * 2, primes);
				}
				prime = primes.get(primeId);
			}
			if (n % prime == 0) {
				n /= prime;
				if (!ret.containsKey(prime)) {
					ret.put(prime, 1);
				} else {
					ret.put(prime, ret.get(prime) + 1);
				}
			} else {
				prime= -1;
			}
		}
		return ret;
	}
	
	public static long product (Iterable<Long> it) {
		long prod = 1;
		for (long l : it) {
			prod *= l;
		}
		return prod;
	}

	public static long product (int[] it) {
		long prod = 1;
		for (long l : it) {
			prod *= l;
		}
		return prod;
	}

	public static boolean isPalindrome (long n) {
		return (""+n).equals(StringUtils.reverse(n+""));
	}
	
	public static void main(String[] args) {
		System.out.println(Long.MAX_VALUE);
	}
	
	/**
	 * returns the nth triangular number
	 * @param n
	 * @return
	 */
	public static long triangle (long n) {
		return (n + n*n)/2;
	}

	public static ArrayList<Long> getDivisors (long n) {
		return getDivisors(n,true);
	}

	public static ArrayList<Long> getDivisors (long n, ArrayList<Long> divisors, boolean proper) {
		if (divisors == null) divisors = new ArrayList<Long>();
		long maxDiv = (long)(Math.sqrt(n) + 1);
		long div = 1;
		if (proper) {
			divisors.add(1L);
			div = 2;
		} 
		while (div < maxDiv) {
			if (n %div == 0) {
				divisors.add(div);
				divisors.add(n/div);
			}
			div++;
		}
		Collections.sort(divisors);
		return divisors;
	}	
	public static ArrayList<Long> getDivisors (long n, boolean proper) {
		return getDivisors(n,null,proper);
	}
	
    static boolean isPandigital (String numStr) {
		int maxDig = 0;
		for (char ch : numStr.toCharArray()) {
			maxDig = (maxDig < Integer.parseInt("" + ch)) ? Integer.parseInt("" + ch) : maxDig; 
		}
		if (maxDig != numStr.length()) return false;
		for (int digit = 1 ; digit < numStr.length() ; digit++) {
			if (!numStr.contains("" + digit)) {
				return false;
			}
		}
		return true;
    }
    
	// test for pandigital
	static boolean isPandigital (long n) {
		return isPandigital(Long.toString(n));
	}    	

	public static boolean isPrime (long n) {
		long maxTest = (long)(Math.sqrt(n) +1) + 1;
		if (n < 2|| (n % 2 == 0)) {
			return false;
		}
		if (n == 3) {
			return true;
		}
		long test = 3;
		double div;
		do  {
			div =(double)n/(double)test;
			if (div == (long)div) {
				return false;
			}
			test += 2;
		} while (test <= maxTest);
		return true;
	}	
	
	public static long reverseNumber (long n) {
		return Long.parseLong(StringUtils.reverse("" + n));
	}
	
	public static boolean isPalindrome (String n) {
		return StringUtils.reverse(n).equals(n);
	}
	
	public static long getPentagonal (long n) {
		return (long)(0.5 * n * (3*n-1));
	}
	
	public static long pentagonalRoot (long l) {
		Double[] sols = solveQuadratic(3, -1, -2*l);
		if (sols == null) {
			return -1;
		}
		double sol = Math.max(sols[0], sols[1]);
		if (sol == (long)sol) {
			return (long)sol;
		}
		return -1;
	}
	
	static public Double[] solveQuadratic (long a, long b, long c) {
		double det = b * b - 4 * a * c;
		Double solutions[] = new Double[2];
		if (det < 0) {
			return null;
		} else {
			det = Math.sqrt(det);
			solutions[0] = (-b - det) / 2 / a;
			solutions[1] = (-b + det) / 2 / a;
		}
		return solutions;
	}
	
	static double product (double n, int terms) {
		double ret = 1;
		for (int idx = 1; idx < terms; idx++) {
			ret *= (1.0 / (1.0 - Math.pow(n, idx)));
		}
		return ret;
	}
	
	static ArrayList<Long> getFactorials (int n) {
		ArrayList<Long> f = new ArrayList<Long>();
		long fa = 1;
		for (int idx =1 ; idx <= n ; idx++) {
			f.add((fa*=idx));
		}
		return f;
	}
	
	public static Long nextPermutation(long l) {
		String s = l + "";
		int digits[] = new int[s.length()];
		int idx = 0;
		for (char c : s.toCharArray()) {
			digits[idx++] = Integer.parseInt(""+c);
		}
		if (!nextPermutation(digits)) {
			return null;
		}
		s = "";
		for (int i = digits.length-1 ; i >= 0 ; i--) {
			s += digits[i];
		}
		return Long.parseLong(s);
	}
    /**
     * Accepts an array of <b>ints</b> and reorders it's elements
     * to recieve lexicographically next permutation
     *
     * @param p permutation
     * @return false, if given array is lexicographically last permutation, true otherwise
     */
    public static boolean nextPermutation(int[] p) {
        int a = p.length - 2;
        while (a >= 0 && p[a] >= p[a + 1]) {
            a--;
        }
        if (a == -1) {
            return false;
        }
        int b = p.length - 1;
        while (p[b] <= p[a]) {
            b--;
        }
        int t = p[a];
        p[a] = p[b];
        p[b] = t;
        for (int i = a + 1, j = p.length - 1; i < j; i++, j--) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
        }
        return true;
    }
	
    public static Long rotateNumber (Long l) {
    	String numberStr;
    	char[] chars; char tmp;
		numberStr = "" + l;
		chars = numberStr.toCharArray();
		tmp = chars[0];
		for (int idx = 0 ; idx < numberStr.length() - 1; idx++) {
			chars[idx] = chars[idx+1]; 
		}
		chars[chars.length-1] = tmp;
		return Long.parseLong(new String(chars));
    }

	public static int charToInt (char ch) {
		if (ch == '0') return 0;
		if (ch == '1') return 1;
		if (ch == '2') return 2;
		if (ch == '3') return 3;
		if (ch == '4') return 4;
		if (ch == '5') return 5;
		if (ch == '6') return 6;
		if (ch == '7') return 7;
		if (ch == '8') return 8;
		if (ch == '9') return 9;
		else return -1;
	}
	
    public static int[] getDigits (Long l) {
    	char[] chars = new String(""+ l).toCharArray();
    	int [] ret = new int[chars.length];
    	for (int idx =0  ; idx < chars.length; idx++) {
    		// not pretty, but quicker than full parsers
    		if (chars[idx] == '0') { ret[idx] = 0; };
    		if (chars[idx] == '1') { ret[idx] = 1; };
    		if (chars[idx] == '2') { ret[idx] = 2; };
    		if (chars[idx] == '3') { ret[idx] = 3; };
    		if (chars[idx] == '4') { ret[idx] = 4; };
    		if (chars[idx] == '5') { ret[idx] = 5; };
    		if (chars[idx] == '6') { ret[idx] = 6; };
    		if (chars[idx] == '7') { ret[idx] = 7; };
    		if (chars[idx] == '8') { ret[idx] = 8; };
    		if (chars[idx] == '9') { ret[idx] = 9; };
    	}
    	return ret;
    }

    public static boolean checkDigitParity (long n,boolean even) {
    	int[] d = getDigits(n);
    	for (int x : d) {
    		if ((x % 2 == 0 && !even) || (x % 2 != 0 && even))
    			return false;
    	}
    	return true;
    }
}
